H2P3

题目

For any positive integers $n$ and $k$ , define $f (n, k)$ as follows. For each way of writing $n$ as an ordered sum of exactly $k$ nonnegative integers, let $S$ be the product of those $k$ integers. Then $f (n, k)$ is the sum of all of the $S$ ’s that are obtained in this way. Find a suitable generating function of $f (n, k)$ , and find the numbers themselves.
Let $f (n, k, c)$ be the number of ways to write $n$ as an ordered sum of exactly $k$ integers, each of which is at least $c$ . Find a suitable generating function of $f (n, k, c)$ , and find the numbers themselves.

依据有序和中的第一个数分类，考虑如果出现 $0$ ，则乘积为 $0$ ：

f (n, k) = {\begin{cases} 0 & , k \geq n + 1 \\ n & , k = 1 \\ \sum_{m = 1}^{n} m f (n - m, k - 1) & , otherwise \end{cases}

令 $f (n, k)$ 的生成函数为 $F (k, x) = \sum_{n = 0}^{\infty} f (n, k) x^{n}$

F (1, x) = \sum_{n = 0}^{\infty} n x^{n} = \frac{x}{(1 - x)^{2}}

当 $k \geq 2$

f (n, k) x^{n} = (\sum_{m = 1}^{n} m f (n - m, k - 1)) x^{n} = \sum_{m = 1}^{n} m f (n - m, k - 1) x^{n}

\begin{aligned} F (k, x) \\ = & \sum_{n = 0}^{\infty} f (n, k) x^{n} \\ = & \sum_{n = 0}^{\infty} \sum_{m = 1}^{n} m f (n - m, k - 1) x^{n - m} x^{m} = \\ = & \sum_{m = 1}^{\infty} m x^{m} \sum_{n = m}^{\infty} f (n - m, k - 1) x^{n - m} = \\ = & \sum_{m = 1}^{\infty} m x^{m} F (k - 1, x) \\ = & \frac{x}{(1 - x)^{2}} F (k - 1, x) \\ = & {(\frac{x}{(1 - x)^{2}})}^{k} \\ = & \frac{x^{k}}{(1 - x)^{2 k}} \end{aligned}

其中

\frac{1}{(1 - x)^{2 k}} = \sum_{n = 0}^{\infty} (\binom{n + 2 k - 1}{2 k - 1}) x^{n}

故

f (n, k) = [x^{n}] F (k, x) = (\binom{n + k - 1}{2 k - 1})

将 $F (k, x)$ 写为 $k$ 个生成函数 $F_{i} (x)$ 之积， $F_{i} (x)$ 对应有序和中第 $i$ 个数

F_{i} (x) = \sum_{n = 1}^{\infty} n x^{n} = \frac{x}{(1 - x)^{2}}

F (k, x) = \prod_{i = 1}^{k} F_{i} (x) = {(\frac{x}{(1 - x)^{2}})}^{k} = \frac{x^{k}}{(1 - x)^{2 k}}

令 $f (n, k)$ 的生成函数为

E (x, z) = \sum_{k = 0}^{\infty} \sum_{n = 0}^{\infty} \frac{f (n, k)}{k!} x^{n} z^{k}

将 $E (x, z)$ 写为无穷个生成函数 $E_{i} (x, z)$ 之积， $E_{i} (x, z)$ 对应有序和中 $i$ 的个数

E_{i} (x, z) = \sum_{k = 0}^{\infty} \frac{i^{k}}{k!} x^{k i} z^{k} = \sum_{k = 0}^{\infty} \frac{(i x^{i} z)^{k}}{k!} = e^{i x^{i} z}

E (x, z) = \prod_{i = 1}^{\infty} E_{i} (x) = \prod_{i = 1}^{\infty} e^{i x^{i} z} = e^{\sum_{i = 1}^{\infty} i x^{i} z} = e^{\frac{x z}{(1 - x)^{2}}} = \sum_{k = 0}^{\infty} \frac{z^{k}}{k!} \frac{x^{k}}{(1 - x)^{2 k}}

f (n, k) = k! [x^{n} z^{k}] E (x, z) = k! \frac{1}{k!} [x^{n}] \frac{x^{k}}{(1 - x)^{2 k}} = (\binom{n + k - 1}{2 k - 1})

沿用第一问 solution 2 的思路：

令 $f (n, k, c)$ 的生成函数为 $G (k, c, x) = \sum_{n = 0}^{\infty} f (n, k, c) x^{n}$

将 $G (k, c, x)$ 写为 $k$ 个生成函数 $G_{i} (x)$ 之积， $G_{i} (x)$ 对应有序和中第 $i$ 个数

G_{i} (x) = \sum_{n = c}^{\infty} x^{c} = \frac{x^{c}}{1 - x}

G (k, c, x) = \prod_{i = 1}^{k} G_{i} (x) = \frac{x^{c k}}{(1 - x)^{k}}

f (n, k, c) = [x^{n}] G (k, c, x) = (\binom{n - c k + k - 1}{k - 1})